package main

import (
	"fmt"
)

/**
执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：1.9 MB, 在所有 Go 提交中击败了77.24%的用户
 */
func spiralOrder(matrix [][]int) []int {

	if len(matrix) == 0 || len(matrix[0]) == 0 { return []int{} }

	n, m := len(matrix), len(matrix[0])

	dx, dy := []int{0, 1, 0, -1}, []int{1, 0, -1, 0}
	st := make([][]bool, n)
	for i := 0; i < n; i++ { st[i] = make([]bool, m) }
	res := []int{}
	for i, x, y, d := 0, 0, 0, 0; i < n * m; i++ {
		res = append(res, matrix[x][y])
		st[x][y] = true

		a, b := x + dx[d], y + dy[d]
		if a < 0 || a >= n || b < 0 || b >= m || st[a][b] {
			d = (d + 1) % 4
			a, b = x + dx[d], y + dy[d]
		}
		x, y = a, b
	}
	return res
}

func main() {

	//matrix := [][]int{
	//	{1, 2, 3},
	//	{4, 5, 6},
	//	{7, 8, 9},
	//}
	matrix := [][]int{
		{3},
		{2},
	}
	fmt.Println(spiralOrder(matrix))
}
